package Data;

import java.util.ArrayList;

public class Heap<E extends Comparable> {
	// <T extends Collection>
	// 这里的限定使用关键字extends，后面可以是类也可以是接口。
	// 但这里的extends已经不是继承的含义了，应该理解为T类型是实现Collection接口的类型，或者T是继承了XX类的类型。
	// 多接口限制
	// 虽然Java泛型简单的用 extends 统一的表示了原有的 extends 和 implements 的概念，但仍要遵循应用的体系，Java
	// 只能继承一个类，但可以实现多个接口，所以你的某个类型需要用 extends
	// 限定，且有多种类型的时候，只能存在一个是类，并且类写在第一位，接口列在后面，也就是：
	// <T extends SomeClass & interface1 & interface2 & interface3>
	
	
	//为定义一个类为泛型类型，需要将泛型类型放在类名之后，如：Heap<E extends Comparable>
	
	//为定义一个方法为泛型类型，要将泛型类型放在方法返回类型之前，如： <E extends Comparable<E>> E max(E o1,E o2)；调用：类1.<String>方法（类型为类1的对象）
	
	//你能使用new E(),new E[]
	
	//泛型类型必须是引用类型，不能是（int,char）等基本类型
	
	private ArrayList<E> list = new ArrayList<>();
	
	//error:public Heap<E>(){}
	public Heap(){
		
	}
	
	public Heap(E[] objects){
		for(int i=0;i<objects.length;i++){
			add(objects[i]);
		}
	}
	
	public void add(E newObject){
		list.add(newObject);
		int currentIndex=list.size()-1;
		//左孩子：2*i+1，右孩子：2*i+2，父节点：(i-1)/2
		while(currentIndex>0){
			int parentIndex=(currentIndex-1)/2;
			if(list.get(currentIndex).compareTo(list.get(parentIndex))>0){
				E tempE=list.get(parentIndex);
				list.set(parentIndex, list.get(currentIndex));
				list.set(currentIndex, tempE);
			}
			else{
				break;
			}
			currentIndex=parentIndex;
		}
	}
	public E remove(){
		if(list.size()==0){
			return null;
		}
		E removeObject =list.get(0);
		list.set(0, list.get(list.size()-1));
		list.remove(list.size()-1);
		
		
		//index->[0,.........list.size()-1]
		int currentIndex=0;
		while(currentIndex<list.size()){
			int leftIndex=2* currentIndex+1;
			int rightindex=leftIndex+1;
			if(leftIndex>=list.size()){
				break;
			}
			
			
			int maxIndex=leftIndex;
			if(rightindex<list.size()){
				if(list.get(leftIndex).compareTo(list.get(rightindex))<0){
					maxIndex=rightindex;
				}
			}
			
			if(list.get(currentIndex).compareTo(list.get(maxIndex))<0){
				E tempE=list.get(maxIndex);
				list.set(maxIndex, list.get(currentIndex));
				list.set(currentIndex,tempE);
				currentIndex=maxIndex;
			}
			else{
				break;
			}
		}
		return removeObject;
	}
	public int getSize(){
		return list.size();
	}
	public E getTop(){
		return list.get(0);
	}
	
}
